//package work.rightAnswer;
//
//import java.util.*;
//
//class Node {
//    public int val;
//    public List<Node> neighbors;
//    public Node() {
//        val = 0;
//        neighbors = new ArrayList<Node>();
//    }
//    public Node(int _val) {
//        val = _val;
//        neighbors = new ArrayList<Node>();
//    }
//    public Node(int _val, ArrayList<Node> _neighbors) {
//        val = _val;
//        neighbors = _neighbors;
//    }
//}
//
//class Solution {
//    public Node cloneGraph(Node node) {
//        if(node==null){
//            return null;
//        }
//        //对于图的这种克隆类题目，很重要的一点是保证节点的单例，所以，这里采用HashMap key:原节点 value：克隆节点
//        //同时HashMap还有防止重复入队的功能
//        HashMap<Node,Node> map = new HashMap<>();
//        map.put(node,new Node(node.val));
//        //遍历用数据结构：队列
//        Queue<Node> queue = new LinkedList<>();
//        queue.offer(node);
//        while (!queue.isEmpty()){
//            //当前节点
//            Node poll = queue.poll();
//            //遍历neighbor节点列表
//            for (Node neighbor : poll.neighbors) {
//                //如果map不包含neighbor了，那么入队
//                if(!map.containsKey(neighbor)){
//                    //neighbor加入队列
//                    queue.offer(neighbor);
//                    //将neighbor和它的克隆节点加入哈希表
//                    map.put(neighbor,new Node(neighbor.val));
//                }
//
//                //如果包含neighbor，那么说明之前遍历过了。但是，当前节点克隆节点的neighbor邻居还是要添加的
//                map.get(poll).neighbors.add(map.get(neighbor));
//            }
//        }
//
//        return map.get(node);
//    }
//}